#include <stdio.h>
#include <stdlib.h>

//初始化队头和队尾指针开始时都为0
int front=0,rear=0;

//二叉树节点结构
typedef struct binaryTreeNode {
    int data;   //数据域
    struct binaryTreeNode * leftChild, * rightChild;    //左右孩子指针
}binaryTreeNode_t, *binaryTree;

//初始化树的函数
void createBinaryTree(binaryTree * T){
    *T = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->data = 1;
    //根节点左孩子
    (*T)->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild = NULL;
    (*T)->leftChild->data = 2;
    (*T)->leftChild->rightChild = NULL;
    //根节点右孩子
    (*T)->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild = NULL;
    (*T)->rightChild->data = 3;
    (*T)->rightChild->rightChild = NULL;
    //根节点左孩子的左孩子
    (*T)->leftChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild->leftChild = NULL;
    (*T)->leftChild->leftChild->data = 4;
    (*T)->leftChild->leftChild->rightChild = NULL;
    //根节点左孩子的右孩子
    (*T)->leftChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->rightChild->leftChild = NULL;
    (*T)->leftChild->rightChild->data = 5;
    (*T)->leftChild->rightChild->rightChild = NULL;
    //根节点右孩子的左孩子
    (*T)->rightChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild->leftChild = NULL;
    (*T)->rightChild->leftChild->data = 6;
    (*T)->rightChild->leftChild->rightChild = NULL;
    //根节点右孩子的右孩子
    (*T)->rightChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->rightChild->leftChild = NULL;
    (*T)->rightChild->rightChild->data = 7;
    (*T)->rightChild->rightChild->rightChild = NULL;
}

//入队函数
void enQueue(binaryTree * tree, binaryTree bt) {
    tree[rear++] = bt;
}

//出队函数
binaryTreeNode_t * deQueue(binaryTree * tree) {
    return tree[front++];
}

//输出函数
void displayNode(binaryTree bt) {
    printf("%d ", bt->data);
}

//后序遍历函数
void levelTraverse(binaryTree Tree) {
    binaryTreeNode_t * bt;
    //采用顺序队列，初始化创建队列数组
    binaryTree a[20];
    //根结点入队
    enQueue(a, Tree);
    //当队头和队尾相等时，表示队列为空
    while(front < rear) {
        //队头结点出队
        bt = deQueue(a);
        displayNode(bt);
        //将队头结点的左右孩子依次入队
        if(bt->leftChild != NULL) {
            enQueue(a, bt->leftChild);
        }
        if(bt->rightChild) {
            enQueue(a, bt->rightChild);
        }
    }
}

int main(int argc, char * argv[]) {
    binaryTree Tree;
    //初始化二叉树
    createBinaryTree(&Tree);
    printf("层次遍历1: \n");
    levelTraverse(Tree);
    return 0;
}